package graphic;
/*
* 有 N 个花园，按从 1 到 N 标记。在每个花园中，你打算种下四种花之一。

paths[i] = [x, y] 描述了花园 x 到花园 y 的双向路径。

另外，没有花园有 3 条以上的路径可以进入或者离开。

你需要为每个花园选择一种花，使得通过路径相连的任何两个花园中的花的种类互不相同。

以数组形式返回选择的方案作为答案 answer，其中 answer[i] 为在第 (i+1) 个花园中种植的花的种类。花的种类用  1, 2, 3, 4 表示。保证存在答案。

 

示例 1：

输入：N = 3, paths = [[1,2],[2,3],[3,1]]
输出：[1,2,3]
示例 2：

输入：N = 4, paths = [[1,2],[3,4]]
输出：[1,2,1,2]
示例 3：

输入：N = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
输出：[1,2,3,4]
 

提示：

1 <= N <= 10000
0 <= paths.size <= 20000
不存在花园有 4 条或者更多路径可以进入或离开。
保证存在答案。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/flower-planting-with-no-adjacent
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class GardenNoAdj {

    public int[] gardenNoAdj(int N, int[][] paths) {
        if(N < 1 || paths == null){
            return new int[0];
        }
        int[] ans = new int[N];
        Node[] nodes = new Node[N];
        for(int i =0 ; i < N; i++){
            nodes[i] = new Node(i+1);
        }

        for(int i = 0; i < paths.length; i ++){
            addNode(nodes[paths[i][0] - 1], paths[i][1]);
            addNode(nodes[paths[i][1] - 1], paths[i][0]);
        }

        for(Node n: nodes){
            int[] colors = new int[4];
            Node neib = n.next;
            while(neib != null){
                int color = ans[neib.value - 1];
                if(color != 0){
                    colors[color - 1] = 1;
                }
                neib = neib.next;
            }

            for(int i = 0; i < colors.length; i ++){
                if(colors[i] == 0){
                    ans[n.value - 1] = i + 1;
                    break;
                }
            }
        }
        return ans;
    }

    private void addNode(Node node, int val){
        while(node.next != null){
            node = node.next;
        }
        node.next = new Node(val);
    }

    public static class Node{
        Node next;
        int value;
        public Node(int val){
            value = val;
        }
    }

//    public int[] gardenNoAdj(int N, int[][] paths) {
//
//        Node[] nodes = new Node[N];
//        for (int i = 0; i < N; i++) {
//            nodes[i] = new Node(null, i + 1);
//        }
//
//        for (int[] item : paths) {
//            addNode(nodes[item[0] - 1], item[1]);
//            addNode(nodes[item[1] - 1], item[0]);
//        }
//        int[] result = new int[N];
//
//        for (Node node : nodes) {
//            int[] colorArray = new int[4];
//            Node curNode = node;
//            while (curNode.next != null) {
//                int color = result[curNode.next.value - 1];
//                if (color != 0) {
//                    colorArray[color -1] = 1;
//                }
//
//                curNode = curNode.next;
//            }
//
//            for (int flower = 1; flower <= 4; flower++) {
//                if (colorArray[flower -1] == 0) {
//                    result[node.value - 1] = flower;
//                    break;
//                }
//            }
//        }
//
//        return result;
//    }
//
//    public void addNode(Node node, int value) {
//        while (node.next != null) {
//            node = node.next;
//        }
//        node.next = new Node(null, value);
//    }
//
//    public static class Node {
//
//        Node next;
//        int value;
//
//        public Node(Node next, int value) {
//            this.next = next;
//            this.value = value;
//        }
//    }

    public static void main(String[] args){
        int[][] paths = new int[][]{{1,2},{3,4}};

        int[] ans = (new GardenNoAdj()).gardenNoAdj(4, paths);
        System.out.println(ans);
    }

}
